Contents of Conclusion

We think evaltrace notation is an effective tool for teaching the key concepts of evaluation in Lisp and other applicative languages. We also find that evaltrace is flexible—extensions to other features of Lisp such as tail-recursion elimination and first-class continuations (CALL/CC) are quite easy to make, though we have not included them here.

Because tracing has been a part of Lisp since the days of Lisp 1.5, we should point out how evaltrace diagrams differ from earlier tracing schemes. Lisp tracing programs usually work by replacing the body of the function to be traced; thus they are only able to show the APPLY part of the evaluation process. This can lead to ambiguities. For example, for the the functions FOO1 and FOO2

$\begin{code} (defun bar (y) y) \strut (defun baz (z) z) \strut (defun foo1 (x) (bar (baz x))) \strut (defun foo2 (x) (baz x) (bar x)) \end{code}$

identical traces are produced in most Lisp implementations, as shown in Figure

. In both cases, BAZ is invoked before BAR. But in the first case BAZ is computing the argument to BAR, while in the second case the calls to BAZ and BAR are independent. This difference is clearly portrayed in the corresponding evaltrace diagrams given in Figure

**Figure:** Ambiguous tracing in Lisp.
$\begin{figure}{\noindent\rule{\textwidth}{.01in}} \par \begin{code} (trace bar b... ...turned 3 3 \end{code}\par\par {\noindent\rule{\textwidth}{.01in}} \end{figure}$

**Figure:** Unambiguous tracing using evaltrace.
$\begin{figure}{\noindent\rule{\textwidth}{.01in}} \par \begin{evaltrace} +--> ;(... ... is 3 \end{evaltrace}\par\par {\noindent\rule{\textwidth}{.01in}} \end{figure}$

Another notation for explaining some aspects of Lisp evaluation is the ``fence'' notation of Winston and Horn [7]. Fence notation focuses on the static structure of lexical contours; it is not concerned with the dynamic process of evaluation, function invocation, and return. While it can represent the environment of a closure as a series of nested fences, it cannot represent the application of closures, nor does it cover macro expansion. Like most Lisp TRACE notations, fence notation has no way to represent the difference between FOO1 and FOO2 above.

We believe evaltrace notation offers a significant improvement over both earlier notations, in terms of scope of coverage, graphical intuitiveness, and extensibility. Its generality also makes it useful for describing the operational semantics of programming languages, and in such a way that program traces can be given as ``two-dimensional'' diagrams. In this respect, evaltrace can be viewed as a pleasant alternative notation for Plotkin's structured operational semantics [2]. This connection to the Plotkin-style semantics is discussed in [6], along with extensions to evaltrace for tail-recursion elimination, first-class continuations, assignment, and multiple closures with a shared parent contour.

We hope that both Lisp novices and educators find the notation to be as useful as we have. In support of this, we have made available a set of L^ATEX macros and a special font for producing evaltrace diagrams similar to the ones in this paper. They are available via anonymous ftp in compressed tar format, from a.ergo.cs.cmu.edu (128.2.250.219), in directory pub/evaltrace, files README and evaltrace.tar.Z. The appendix gives a brief guide on the use of these macros and font.